閱讀前，建議可以參考Day1：閱讀指南＆為何選擇這個題目？

▌挑戰簡介

• 題目：計算機概論Ｘ30天

• 挑戰內容：連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程，還有自己學習程式的心得體悟。

• 本篇性質：

  • 適合的人：對密碼學、大數處理有興趣的人，因為模數運算（mod）、費馬小定理很常拿來用
  • 一定要讀過Day 14:[離散數學]同餘（Mod）是什麼？Day 18:[離散數學]歐拉定理

▌超難問題

這是一個被費馬坑了的故事

費馬小定理解法

在Day 17:[離散數學] 用費馬小定理處理超大難題

我記錄了自己用假日一個早上的時間，費馬小定理解決了「23^4800017 除以35餘數是多少？」這個問題

當時我覺得自己真是天才，竟然可以想到如此精妙的算法

23^6 ≡1 mod 7  //根據費馬小定理
23^4 ≡1 mod 5  //根據費馬小定理
23^12 ≡1 mod 7  //同餘的相乘性質的次方性質
23^12 ≡1 mod 5  //同餘的相乘性質的次方性質
6X23^12 ≡6X1 mod 7  //這個轉換很精妙，請自行體悟一下
6X23^12 ≡6X1 mod 5  //這個轉換很精妙，請自行體悟一下
6X23^12 ≡-1 mod 7
6X23^12 ≡ 1 mod 5 
7|6X23^12+1 // 同餘的因數定理
5|6X23^12-1  //同餘的因數定理
35|(6X23^12+1)(6X23^12-1)
35|(6^2X23^24)-1
6^2X23^24 ≡ 1 mod 35 //同餘的因數定理
36 X 23^24 ≡1 mod 35 
23^24 ≡1 mod 35  //因為 36 ≡1 mod 35 因此可以消掉
23^4800017  ≡ (23^24)2000000 X 23^17   mod 35
23^17  mod 35  //因為 23^24 ≡1 mod 35 因此(23^24)2000000 可以消掉
太好了，千辛萬苦終於把23^4800017  mod 35 變成 23^17  mod 35 這個較小的問題
23^17 mod 35 
23^2 ≡  4  mod 35  //這條要自己算
(23^2)8 X 23  ≡  4^8 X 23  mod 35 
4^4 ≡  11  mod 35 //這條要自己算
4^8 X 23   ≡ 11^2 X23 mod 35 
11^2 X23 ≡ 18 mod 35 

但是當我認識歐拉定理
我覺得....幹！！費馬小定理根本難用到爆炸

歐拉定理解法

以下是歐拉定理的解法

因為23和35互質，23^φ(35)≡1 (mod35)

φ(35)=24

因此23^24≡1  (mod35)
23^4800017  ≡ (23^24)2000000 X 23^17   mod 35
23^17   mod 35
23^2 ≡  4  mod 35  //這條要自己算
(23^2)8 X 23  ≡  4^8 X 23  mod 35 
4^4 ≡  11  mod 35 //這條要自己算
4^8 X 23   ≡ 11^2 X23 mod 35 
11^2 X23 ≡ 18 mod 35 

整整少了14行！！！！！！

▌總結

• 歐拉定理完勝費馬小定理，而且適用性更高
• 知識就是力量，使用好的知識工具處理問題，效率永遠是不知道的好幾倍